package leetcode_day._2021._202106._1120;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/30 18:15
 * 数位成本和为目标值的最大数字
 * 算法：动态规划
 * 完全背包问题
 * 有若干物品，求给定费用下，花光所有费用所能选择的最大价值是多少
 * 这里的最大价值指数字的数量
 * 还要满足恰好装满
 */
public class _12_1449 {
    public static void main(String[] args) {
        System.out.println(new _12_1449().largestNumber(new int[]{4, 3, 2, 5, 6, 7, 2, 5, 5}, 9));
//        System.out.println(new _12_1449().method(new int[]{7, 7, 4}, new int[]{1, 1, 1}, 10));
    }

    public int method(int[] w, int[] p, int bg) {
        int[] dp = new int[bg + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 0; i < w.length; i++) {
            for (int j = w[i]; j <= bg; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bg];
    }

    public String largestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= 9; i++) {
            int w = cost[i - 1];
            for (int j = w; j <= target; j++) dp[j] = Math.max(dp[j], dp[j - w] + 1);
        }
        System.out.println(Arrays.toString(dp));
        // 除非刚好填满, 不然就会小于 0
        if (dp[target] < 0) return "0";
        StringBuilder ans = new StringBuilder();
        // 贪心
        for (int i = 9, j = target; i >= 1; i--) {
            int w = cost[i - 1];
            while (j >= w && dp[j] == dp[j - w] + 1) {
                ans.append(i);
                j -= w;
            }
        }
        return ans.toString();
    }

}
